package mergeLinkedList;

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = null ;
        ListNode tail = null ;
        while(list1 !=  null || list2 != null){
            if(list1 == null || ( list2 != null && list2.getVar() < list1.getVar())){
                if(tail!= null){
                    tail.setNext(list2);
                    tail = list2;
                }else{
                    tail = head = list2;
                }
                list2 = list2.getNext();
            }
            if((list2 == null && list1 != null) || ( list1 != null && list1.getVar() <= list2.getVar())){
                if(tail != null){
                    tail.setNext(list1);
                    tail = list1 ;
                }else {
                    tail = head = list1;
                }
                list1 = list1.getNext();
            }
        }
        return head ;
    }
    private void forNodes(ListNode head){
        ListNode next = head ;
        do{
            System.out.println(next.getVar());
        }while((next = next.getNext()) != null);
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode s1 =  new ListNode(1);
        ListNode s2 =  new ListNode(4);
        ListNode s3 =  new ListNode(6);
        ListNode s4 =  new ListNode(7);
        s1.setNext(s2);
        s2.setNext(s3);
        s3.setNext(s4);

        ListNode s5 =  new ListNode(2);
        ListNode s6 =  new ListNode(3);
        ListNode s7 =  new ListNode(5);
        ListNode s8 =  new ListNode(8);

        s5.setNext(s6);
        s6.setNext(s7);
        s7.setNext(s8);

        solution.forNodes(solution.Merge(s1 , s5));
    }
}
